# ---
# title: 878. Nth Magical Number
# id: problem878
# author: Tian Jun
# date: 2020-10-31
# difficulty: Hard
# categories: Math, Binary Search
# link: <https://leetcode.com/problems/nth-magical-number/description/>
# hidden: true
# ---
# 
# A positive integer is _magical_  if it is divisible by either A or B.
# 
# Return the N-th magical number.  Since the answer may be very large, **return
# it modulo**`10^9 + 7`.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: N = 1, A = 2, B = 3
#     Output: 2
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: N = 4, A = 2, B = 3
#     Output: 6
#     
# 
# **Example 3:**
# 
#     
#     
#     Input: N = 5, A = 2, B = 4
#     Output: 10
#     
# 
# **Example 4:**
# 
#     
#     
#     Input: N = 3, A = 6, B = 4
#     Output: 8
#     
# 
# 
# 
# **Note:**
# 
#   1. `1 <= N <= 10^9`
#   2. `2 <= A <= 40000`
#   3. `2 <= B <= 40000`
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
